
import java.util.ArrayList;

import org.omg.Messaging.SYNC_WITH_TRANSPORT;

import com.vividsolutions.jts.geom.Geometry;
import com.vividsolutions.jts.geom.GeometryFactory;
import com.vividsolutions.jts.geom.MultiLineString;
import com.vividsolutions.jts.geom.MultiPolygon;
import com.vividsolutions.jts.geom.Polygon;
import com.vividsolutions.jts.io.ParseException;
import com.vividsolutions.jts.io.WKTReader;

class TreeNode {
	String Geohash;
	boolean Selected;
	TreeNode leftChild;
	TreeNode rightChild;
	public String getData(){
		return Geohash;
	}
	public TreeNode getLchild(){
		return leftChild;
	}
	public TreeNode getRchild(){
		return rightChild;
	}
	public void setNode(String Geohash,boolean Selected,TreeNode lc,TreeNode rc){
		this.Geohash=Geohash;
		this.Selected=Selected;
		leftChild=lc;
		rightChild=rc;
	}
	public TreeNode(){
		
	}

}
class Counter{  
    public static int count=0;  
}  
  
public class TreeTest  
{  
	public final static int MAXLEVEL=23;/*面数据的最大划分次数*/
	public final static int MAXSEARCHLEVEL=17;/*查询范围的最大划分次数*/
	static ArrayList<String> polarrayList=new ArrayList<String>();
	static ArrayList<String> linearrayList=new ArrayList<String>();
	static ArrayList<String> rangearrayList=new ArrayList<String>();
	static ArrayList<String> pointrangearrayList=new ArrayList<String>();
//	public int getMavlevel(int MAXLEVEL){
//		return this.MAXLEVEL=MAXLEVEL;
//	}
    public static TreeNode createTree(TreeNode root, String geohash,int level)  
    {  
        if(geohash.length()<=level) 
        {
		    TreeNode tl = new TreeNode();  
		    TreeNode tr = new TreeNode();  
		    root.setNode(geohash,false,createTree(tl,geohash+'0',level),createTree(tr,geohash+'1',level));       
        }  
        else{
        	root=null;
        }
        return root;  
    }
    public static void traverse(TreeNode root)  
    {  
        if(root!= null)  
        {  
//            System.out.println(root.getData());  
            traverse(root.getLchild());  
            traverse(root.getRchild());  
        }  
    } 
    public static void getResult(TreeNode root){
    	    if(root!=null&&root.Selected==true)
    	    {
//	    	    	System.out.println(root.getData()); 
	    	    	getResult(root.getLchild());
	    	    	getResult(root.getRchild());
    	    }
    }
   /*面数据处理*/
    public void geohashPolFunc(Geometry A,TreeNode node,int level) throws ParseException{
    	/*若当前单元网格划分次数达到了最大划分次数
    	 * 那么选中当前结点node
    	 * */
    	    if(level==MAXLEVEL){
	    		node.Selected=true;
	    		return;
	    	}  	 
    	    /*若node子结点的划分次数大于等于查询区域的最大划分次数并且面数据包含node的左子结点
    	     * 则选中node的左子结点
    	     * */
	    	if(level>=MAXSEARCHLEVEL-1&&dataContains(A,node.leftChild)){
	    		node.leftChild.Selected=true;
	    	}
	    	 /*若node子结点的划分次数大于等于查询区域的最大划分次数并且面数据与node的左子结点相交
	    	  * 且相交部分面积占左子结点面积的一半以上
    	     * 则选中node的左子结点
    	     * */
	    	else if(level>=MAXSEARCHLEVEL-1&&dataOverlaps(A,node.leftChild)&&areaRatio(A,node.leftChild)>0.5){
    			node.leftChild.Selected=true;
    		}
	        /*否则 若查询区域与左子结点有交集则继续递归查询*/
	    	else if(dataIntersects(A,node.leftChild)){
	    		if(!dataTouches(A,node.leftChild)){
	    			geohashPolFunc(A, node.leftChild, level+1);
	    		}
	    	}
	    	if(level>=MAXSEARCHLEVEL-1&&dataContains(A,node.rightChild)){
	    		node.rightChild.Selected=true;
	    	}
	    	else if(level>=MAXSEARCHLEVEL-1&&dataOverlaps(A,node.rightChild)&&areaRatio(A,node.rightChild)>0.5){
    			node.rightChild.Selected=true;
    		}
	    	else if(dataIntersects(A,node.rightChild)){
	    		if(!dataTouches(A,node.rightChild)){
	    			geohashPolFunc(A,node.rightChild,level+1);
	    		}
	    	}
	    	if(node.rightChild.Selected&&node.leftChild.Selected&&level>=MAXSEARCHLEVEL){
	    		node.Selected=true;
	    	}
	    	else {
		    if(node.leftChild.Selected)
				polarrayList.add(node.leftChild.getData());
			if(node.rightChild.Selected)
				polarrayList.add(node.rightChild.getData());
		    }
    }
    public void geohashLineFunc(Geometry A,TreeNode node,int level) throws ParseException {
    	if(level==MAXLEVEL-1&&dataIntersects(A, node.leftChild)){
    	     node.leftChild.Selected=true;
    	}
    	else if(dataIntersects(A, node.leftChild)){
    	     geohashLineFunc(A, node.leftChild, level+1);
    	}
    	if(level==MAXLEVEL-1&&dataIntersects(A, node.rightChild)){
	    	 node.rightChild.Selected=true;
	    }
	    else if(dataIntersects(A, node.rightChild)){
	    	 geohashLineFunc(A, node.rightChild, level+1);
	    }
		if(node.leftChild.Selected){
			 linearrayList.add(node.leftChild.getData());
		}
		else if(node.rightChild.Selected){
			 linearrayList.add(node.rightChild.getData());
		}
	}
    public void pointRangeFunc(Polygon A,TreeNode node,int level,int ogrinal) throws ParseException{
    	 if(level==MAXSEARCHLEVEL){
	    		node.Selected=true;
	    		return;
	    	}  	    
	    	if(dataContains(A,node.leftChild)){
	    		node.leftChild.Selected=true;
	    	}
	    	else if(dataOverlaps(A,node.leftChild)&&areaRatio(A,node.leftChild)>0.5){
 			node.leftChild.Selected=true;
 		   }
	    	else if(dataIntersects(A,node.leftChild)){
	    		if(!dataTouches(A,node.leftChild)){
	    			pointRangeFunc(A, node.leftChild, level+1,ogrinal);
	    		}
	    	}
	    	if(dataContains(A,node.rightChild)){
	    		node.rightChild.Selected=true;
	    	}
	    	else if(dataOverlaps(A,node.rightChild)&&areaRatio(A,node.rightChild)>0.5){
 			node.rightChild.Selected=true;
 		}
	    	else if(dataIntersects(A,node.rightChild)){
	    		if(!dataTouches(A,node.rightChild)){
	    			pointRangeFunc(A,node.rightChild,level+1,ogrinal);
	    		}
	    	}
	    	if(node.rightChild.Selected&&node.leftChild.Selected){
	    		node.Selected=true;
	    		if(level==ogrinal){
	    		 	pointrangearrayList.add(node.getData());
	    		}
	    	}
	    	else {
		    if(node.leftChild.Selected)
		    	pointrangearrayList.add(node.leftChild.getData());
			if(node.rightChild.Selected)
			pointrangearrayList.add(node.rightChild.getData());
		}
    }
    /*基于点的范围查询修改后的查询范围处理算法
     * 参数Polygon A为查询范围的Geometry，TreeNode node是以level层级为根,ogrinal为初始的level值，level1为最大划分次数
     * */
    public void pointRangeFunc1(Polygon A,TreeNode node,int level,int ogrinal,int level1) throws ParseException{
   	    if(level==level1){
	    		node.Selected=true;
	    		if(level==ogrinal){
	    			pointrangearrayList.add(node.getData());
	    		}
	    		return;
	    	}
   	    /* 若查询范围包含node的左孩子*/
	    	if(dataContains(A,node.leftChild)){
	    		node.leftChild.Selected=true;
	    	}
	    	/* 若查询范围与node的左孩子相交且，相交部分的面积占node左孩子的一半以上*/
	    	else if(dataOverlaps(A,node.leftChild)&&areaRatio(A,node.leftChild)>0.5){
			node.leftChild.Selected=true;
		   }
	    	/* 若前面的条件都不满足，且查询范围与node的左孩子有交集则递归继续划分*/
	    	else if(dataIntersects(A,node.leftChild)){
	    		if(!dataTouches(A,node.leftChild)){
	    			pointRangeFunc1(A, node.leftChild, level+1,ogrinal,level1);
	    		}
	    	}
	    	if(dataContains(A,node.rightChild)){
	    		node.rightChild.Selected=true;
	    	}
	    	else if(dataOverlaps(A,node.rightChild)&&areaRatio(A,node.rightChild)>0.5){
			node.rightChild.Selected=true;
		}
	    	else if(dataIntersects(A,node.rightChild)){
	    		if(!dataTouches(A,node.rightChild)){
	    			pointRangeFunc1(A,node.rightChild,level+1,ogrinal,level1);
	    		}
	    	}
	    	if(node.rightChild.Selected&&node.leftChild.Selected){
	    		node.Selected=true;
	    		if(level==ogrinal){
	    		 	pointrangearrayList.add(node.getData());
	    		}
	    	}
	    	else {
		    if(node.leftChild.Selected)
		    	pointrangearrayList.add(node.leftChild.getData());
			if(node.rightChild.Selected)
			pointrangearrayList.add(node.rightChild.getData());
		}
   }
    public void geohashSearchFunc(Polygon A,TreeNode node,int level) throws ParseException{
    	if(level==MAXSEARCHLEVEL){
    		node.Selected=true;
    	}
    	else{
    		 /* 查询区域与该结点的左孩子不相交，则它一定与右结点相交*/
    		if(!(dataIntersects(A, node.leftChild)&&!dataTouches(A, node.leftChild))){
    			//System.out.println("1");
    			geohashSearchFunc(A, node.rightChild, level+1);
    		}
    		else{
    			/* 查询区域与该结点的右孩子不相交，则它一定与左结点相交*/
    			if(!(dataIntersects(A, node.rightChild)&&!dataTouches(A, node.rightChild))){
    				//System.out.println("2");
    				geohashSearchFunc(A, node.leftChild, level+1);
    			}
    			else
    				/* 查询区域与该结点的左孩子和右孩子都相交，则选择该结点*/
    				node.Selected=true;
    		}
    	}
    	if(node.Selected==true){
    		rangearrayList.add(node.getData());
    	}
    }
    /*基于点的范围查询修改前的查询范围处理算法
     * 参数Polygon A为查询范围的Geometry，TreeNode node是以level层级为根，level1为最大划分次数
     * */
    public void geohashSearchFunc1(Polygon A,TreeNode node,int level,int level1) throws ParseException{
    	/*level 等于最大划分次数则该结点加入结果集*/
    	if(level==level1){
    		node.Selected=true;
    	}
    	else{
    		if(!(dataIntersects(A, node.leftChild)&&!dataTouches(A, node.leftChild))){
    			geohashSearchFunc1(A, node.rightChild, level+1,level1);
    		}
    		else{
    			if(!(dataIntersects(A, node.rightChild)&&!dataTouches(A, node.rightChild))){
    				geohashSearchFunc1(A, node.leftChild, level+1,level1);
    			}
    			else
    				node.Selected=true;
    		}
    	}
    	if(node.Selected==true){
    		rangearrayList.add(node.getData());
    	}
    }
    private boolean dataTouches(Geometry a, TreeNode leftChild) throws ParseException {
      	Polygon polygon=turnPol(leftChild);
		return a.touches(polygon);
	}
	private boolean dataOverlaps(Geometry a, TreeNode leftChild) throws ParseException {
		Polygon polygon=turnPol(leftChild);
		return a.overlaps(polygon);
	}
	private Polygon turnPol(TreeNode leftChild) throws ParseException{
      	Geohash geohash=new Geohash();
		double dianji[]=geohash.bitdecode(leftChild.getData());
		GeometryFactory geometryFactory=new GeometryFactory();
		WKTReader reader = new WKTReader(geometryFactory);
		String polygonstring="POLYGON(("+String.valueOf(dianji[0])+" "+String.valueOf(dianji[2])+","+" "+String.valueOf(dianji[0])+" "+String.valueOf(dianji[3])+","+" "+String.valueOf(dianji[1])+" "+String.valueOf(dianji[3])+","+" "+String.valueOf(dianji[1])+" "+String.valueOf(dianji[2])+","+" "+String.valueOf(dianji[0])+" "+String.valueOf(dianji[2])+"))";
		Polygon polygon = (Polygon) reader.read(polygonstring); 
		return polygon; 	
    }
	public static boolean Choose(Polygon searchpol,String geohashstring) throws ParseException{
		Geohash geohash=new Geohash();
		double dianji[]=geohash.bitdecode(geohashstring);
		GeometryFactory geometryFactory=new GeometryFactory();
		WKTReader reader = new WKTReader(geometryFactory);
		String polygonstring="POLYGON(("+String.valueOf(dianji[0])+" "+String.valueOf(dianji[2])+","+" "+String.valueOf(dianji[0])+" "+String.valueOf(dianji[3])+","+" "+String.valueOf(dianji[1])+" "+String.valueOf(dianji[3])+","+" "+String.valueOf(dianji[1])+" "+String.valueOf(dianji[2])+","+" "+String.valueOf(dianji[0])+" "+String.valueOf(dianji[2])+"))";
		Polygon polygon = (Polygon) reader.read(polygonstring); 
		if(polygon.intersects(searchpol)&&!polygon.touches(searchpol))
		return true;
		else {
			return false;
		}
	}
    private double areaRatio(Geometry a, TreeNode leftChild) throws ParseException {//计算面积比值
//		System.out.println(leftChild.getData());
    	    Polygon polygon=turnPol(leftChild);
		Geometry geometry=a.intersection(polygon);
//		Geometry squaregeometry=geometry.getEnvelope();
		double squarearea=geometry.getArea();
		double geohasharea=polygon.getArea();
		return squarearea/geohasharea;	
	}
	private boolean dataIntersects(Geometry a, TreeNode leftChild) throws ParseException {//计算leftchild对应的geohash区域与面数据是否相交
		Polygon polygon=turnPol(leftChild);
	    return a.intersects(polygon);
	}
	private boolean dataContains(Geometry a, TreeNode leftChild) throws ParseException {//计算面数据是否包含leftchild对应的geohash区域
		Polygon polygon=turnPol(leftChild);
		return a.contains(polygon);
	}
	public static void main(String [] args) throws ParseException{
    String geohash="";
    	TreeNode root=new TreeNode();
    	root=createTree(root,"1",MAXSEARCHLEVEL);
    	GeometryFactory geometryFactory=new GeometryFactory();
	WKTReader reader = new WKTReader(geometryFactory);
    	Polygon polygon1 = (Polygon) reader.read("POLYGON((10 -90, 10 90, 180 90, 180 -90, 10 -90))"); 
    	TreeTest rTest=new TreeTest();
    	rTest.pointRangeFunc1(polygon1, root, 0,0,1);
	for(int j=0;j<TreeTest.pointrangearrayList.size();j++){
		System.out.println(TreeTest.pointrangearrayList.get(j));
	 }
    }
}
